package com.practice.niuke.new_direct_basics.class09;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Stack;

/**
 * 岛问题
 * 【题目】
 * 一个矩阵中只有0和1两种值， 每个位置都可以和自己的上、 下、 左、 右 四个位置相连， 如
 * 果有一片1连在一起， 这个部分叫做一个岛， 求一个矩阵中有多少个岛?
 * 【举例】
 * 001010
 * 111010
 * 100100
 * 000000
 * 这个矩阵中有三个岛
 */
public class Code03_Islands {

    public static int countIslands1(int[][] m) {
        if (m == null || m[0] == null) {
            return 0;
        }
        int N = m.length;
        int M = m[0].length;
        int res = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (m[i][j] == 1) {
                    res++;
                    infect(m, i, j, N, M);
                }
            }
        }
        return res;
    }

    public static void infect(int[][] m, int i, int j, int N, int M) {
        if (i < 0 || i >= N || j < 0 || j >= M || m[i][j] != 1) {
            return;
        }
        m[i][j] = 2;
        infect(m, i + 1, j, N, M);
        infect(m, i - 1, j, N, M);
        infect(m, i, j + 1, N, M);
        infect(m, i, j - 1, N, M);
    }


    // ==================================并查集代码（开始）===========================================

    /**
     * 并查集结构中，每个集合的元素（节点）类
     *
     * @param <V>
     */
    public static class Element<V> {
        /**
         * 元素值
         */
        public V value;

        /**
         * 指向上一个节点的指针
         *
         * @param value
         */
        public Element(V value) {
            this.value = value;
        }

    }

    /**
     * 并查集结构
     *
     * @param <V>
     */
    public static class UnionFindSet<V> {
        // HashMap<节点a的值，节点a>：key为“节点a的值”，value为“节点a”
        public HashMap<V, Code04_UnionFind.Element<V>> elementMap;
        // HashMap<节点a, 节点a的父节点>
        public HashMap<Code04_UnionFind.Element<V>, Code04_UnionFind.Element<V>> fatherMap;
        // sizeMap中的key，每一个key都一定是集合的头节点（代表节点）。
        // HashMap<节点a, 节点a所代表的集合的元素个数>
        public HashMap<Code04_UnionFind.Element<V>, Integer> sizeMap;

        /**
         * 构造函数(初始化)
         *
         * @param list 样本集合（节点值集合）
         */
        public UnionFindSet(List<V> list) {
            elementMap = new HashMap<>();
            fatherMap = new HashMap<>();
            sizeMap = new HashMap<>();
            for (V value : list) {
                Code04_UnionFind.Element<V> element = new Code04_UnionFind.Element<V>(value);
                elementMap.put(value, element);
                fatherMap.put(element, element);
                sizeMap.put(element, 1);
            }
        }

        /**
         * 查询一个节点的头节点，
         * 从输入参数element出发，往上一直找，找到不能再往上的头节点返回。
         * 往上找的过程中，把经过的节点全部扁平化（都直接挂在头节点下）。
         *
         * @param element element
         * @return Element
         */
        private Code04_UnionFind.Element<V> findHead(Code04_UnionFind.Element<V> element) {
            // 把往上找的过程中，沿途经过的节点都记录在path栈中
            Stack<Code04_UnionFind.Element<V>> path = new Stack<>();
            // 一个节点的父节点不是自己就一直往上找，直到来到头节点（代表节点）。
            while (element != fatherMap.get(element)) {
                path.push(element);
                element = fatherMap.get(element);
            }
            // 把往上找的过程中，沿途经过的节点都直接挂在头节点（代表节点）下。
            while (!path.isEmpty()) {
                fatherMap.put(path.pop(), element);
            }
            return element;
        }

        /**
         * 判断两个元素是否属于同一个集合
         *
         * @param a 第一个元素的值
         * @param b 第二个元素的值
         * @return boolean
         */
        public boolean isSameSet(V a, V b) {
            if (elementMap.containsKey(a) && elementMap.containsKey(b)) {
                return findHead(elementMap.get(a)) == findHead(elementMap.get(b));
            }
            return false;
        }

        /**
         * 合并两个元素所在的集合
         *
         * @param a 第一个元素的值
         * @param b 第二个元素的值
         */
        public void union(V a, V b) {
            if (elementMap.containsKey(a) && elementMap.containsKey(b)) {
                Code04_UnionFind.Element<V> aF = findHead(elementMap.get(a));
                Code04_UnionFind.Element<V> bF = findHead(elementMap.get(b));
                if (aF != bF) {
                    Code04_UnionFind.Element<V> big = sizeMap.get(aF) >= sizeMap.get(bF) ? aF : bF;
                    Code04_UnionFind.Element<V> small = big == aF ? bF : aF;
                    fatherMap.put(small, big);
                    sizeMap.put(big, sizeMap.get(aF) + sizeMap.get(bF));
                    sizeMap.remove(small);
                }
            }
        }

        /**
         * 获取“并查集”中集合的个数（代表节点的个数）
         *
         * @return int
         */
        public int getSetNum() {
            return sizeMap.size();
        }

    }
    // ==================================并查集代码（结束）===========================================

    /**
     * 使用并查集查询有多少个岛
     *
     * @param m 输入的二维数组
     * @return int
     */
    public static int countIslands2(int[][] m) {
        // 位置集合
        List<String> list = new ArrayList<>();
        // 把所有值为1的位置都记录下来了，加入到位置集合中。
        for (int row = 0; row < m.length; row++) {
            for (int col = 0; col < m[0].length; col++) {
                if (m[row][col] == 1) {
                    // row,col为5，3 ----> 5_3
                    String position = String.valueOf(row) + "_" + String.valueOf(col);
                    list.add(position);
                }
            }
        }
        // 生成一个并查集
        // 此时所有值为1的位置自己单独组成集合，没有任何联通的情况
        UnionFindSet<String> unionSet = new UnionFindSet<>(list);
        // 将上、下、左、右相邻且都为1的位置，在并查集中联通（集合合并）
        for (int row = 0; row < m.length; row++) {
            for (int col = 0; col < m[0].length; col++) {
                if (m[row][col] == 1) {
                    // row,col为5，3 ----> 5_3
                    String position = String.valueOf(row) + "_" + String.valueOf(col);
                    if (row - 1 >= 0 && m[row - 1][col] == 1) {
                        String up = String.valueOf(row - 1) + "_" + String.valueOf(col);
                        unionSet.union(up, position);
                    }
                    if (row + 1 < m.length && m[row + 1][col] == 1) {
                        String down = String.valueOf(row + 1) + "_" + String.valueOf(col);
                        unionSet.union(down, position);
                    }
                    if (col - 1 >= 0 && m[row][col - 1] == 1) {
                        String left = String.valueOf(row) + "_" + String.valueOf(col - 1);
                        unionSet.union(left, position);
                    }
                    if (col + 1 < m[0].length && m[row][col + 1] == 1) {
                        String right = String.valueOf(row) + "_" + String.valueOf(col + 1);
                        unionSet.union(right, position);
                    }
                }
            }
        }
        // 返回集合个数（代表节点个数）
        return unionSet.getSetNum();
    }


    public static void main(String[] args) {
        int[][] m1 = {
                {0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 1, 1, 1, 0, 1, 1, 1, 0},
                {0, 1, 1, 1, 0, 0, 0, 1, 0},
                {0, 1, 1, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 1, 1, 0, 0},
                {0, 0, 0, 0, 1, 1, 1, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0},
        };
        System.out.println(countIslands1(m1));
        int[][] m11 = {
                {0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 1, 1, 1, 0, 1, 1, 1, 0},
                {0, 1, 1, 1, 0, 0, 0, 1, 0},
                {0, 1, 1, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 1, 1, 0, 0},
                {0, 0, 0, 0, 1, 1, 1, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0},
        };
        System.out.println(countIslands2(m11));

        int[][] m2 = {
                {0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 1, 1, 1, 1, 1, 1, 1, 0},
                {0, 1, 1, 1, 0, 0, 0, 1, 0},
                {0, 1, 1, 0, 0, 0, 1, 1, 0},
                {0, 0, 0, 0, 0, 1, 1, 0, 0},
                {0, 0, 0, 0, 1, 1, 1, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0},
        };
        System.out.println(countIslands1(m2));
        int[][] m22 = {
                {0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 1, 1, 1, 1, 1, 1, 1, 0},
                {0, 1, 1, 1, 0, 0, 0, 1, 0},
                {0, 1, 1, 0, 0, 0, 1, 1, 0},
                {0, 0, 0, 0, 0, 1, 1, 0, 0},
                {0, 0, 0, 0, 1, 1, 1, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0},
        };
        System.out.println(countIslands2(m22));

    }

}
